package com.pandawhale.algorithm.linked;

import java.util.ArrayList;

public class Linked {


    //数组的特点，在内存中是连续的

    //数组容易产生空间碎片。（严重）
    //数组容易导致内存不足。（严重）
    //因为数组的长度是固定的，所以数组不利于插入和删除节点（一般）

    //数组优点
    //数组查询速度快：查询第N个元素。通过数组起点偏移N-1个位置，拿到第N个元素。（一般）
    //存储密度大（很小）
    //遍历速度快（很小）

    //线性数据结构
    //不易导致空间碎片（很大）
    //能够利用碎片空间（很大）
    //因为链表的长度不是固定的，所以可以很轻易的插入和删除节点。
    //存储密度小。最小是数组的50%。（很小）

    public static class Node {
        public int value;
        public  Node next;

        public static Node create(int value) {
            Node node = new Node();
            node.value = value;
            node.next = null;
            return node;
        }
    }



    //单向链表的每个节点都认为自己是根节点。
    //链表中的每个节点都不知道自己的链表有多长。

    public static void main(String[] args) {
        Node node1 = Node.create(1);
        Node node2 = Node.create(2);
        Node node3 = Node.create(3);
        Node node4 = Node.create(4);
        Node node5 = Node.create(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

//        Node result = turnBack3(node1);
//        printValue(result);
//        int a = 23235;
//        int b = 45647;
//        a = a + b;
//        b = a - b;
//        a = a - b;
//        System.out.println(a);
//        System.out.println(b);

    }

    public static void printValue(Node node) {
        Node now = node;
        while(now != null) {
            System.out.println(now.value);
            now = now.next;
        }
    }

    public static void printValue2(Node node) {
        if (node == null) return;
        System.out.println(node.value);
        printValue2(node.next);
    }

    public static boolean exist(Node node, int value) {
        Node now = node;
        while(now != null) {
            if (now.value == value) {
                return true;
            }
            now = now.next;
        }
        return false;
    }

    public static Node turnBack(Node node) {
        ArrayList<Node> list = new ArrayList<>();

        Node now = node;
        while(now != null) {
            list.add(now);
            now = now.next;
        }

        Node root = list.get(list.size() - 1);
        Node p = root;
        Node q = root;
        for (int i = 0 ; i < list.size() - 1 ; i ++) {
            q = list.get(list.size() - i - 2);
            p.next = q;
            q.next = null;
            p = q;
        }
        return root;
    }

    public static Node turnBack2(Node node) {
        Node r = null;
        Node p = node;
        Node q = node.next;

        while (true) {
            p.next = r;
            if (q == null) {
                return p;
            }
            r = p;
            p = q;
            q = q.next;
        }
    }

    public static Node turnBack3(Node node) {
        if (node.next == null) return node;
        Node root = turnBack3(node.next);
        node.next.next = node;
        node.next = null;
        return root;
    }

}
